package com.monkeyboy.tree;

import com.monkeyboy.TreeNode;

import java.lang.reflect.Array;
import java.util.ArrayList;

/**
 * 二叉树的下一个节点
 * 题目：
 * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回 。
 * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 * <p>
 * 解题思路：
 * 先根据给的节点找到这个二叉树的根节点，然后求出中序序列放到一个list里面，然后再根据给定的值求下一个节点。
 *
 * @Author Gavin
 * @date 2021.04.18 11:12
 */
public class Tree02 {
    public static ArrayList<TreeNode> list = new ArrayList<>();

    public TreeNode solution(TreeNode node) {
        TreeNode root = node;
        while (node != null) {
            node = node.next;
        }
        inOrder(root);
        for (int i = 0; i < list.size(); i++) {
            if (node == list.get(i)) {
                return i == list.size() - 1 ? null : list.get(i + 1);
            }
        }
        return null;
    }

    void inOrder(TreeNode pNode) {
        if (pNode != null) {
            inOrder(pNode.left);
            list.add(pNode);
            inOrder(pNode.right);
        }
    }
}

class test {
    public static ArrayList<TreeNode> list = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left1 = new TreeNode(2);
        TreeNode right = new TreeNode(3);
        root.left = left1;
        root.right = right;
        inOrder(root);
        for (TreeNode pre : list) {
            System.out.print(pre.val + " ");
        }
    }

    static void inOrder(TreeNode pNode) {
        if (pNode != null) {
            inOrder(pNode.left);
            inOrder(pNode.right);
            list.add(pNode);
        }
    }
}
